Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.     

About the Notion of Semiring of Sets

We introduce a generalized notion of semiring and prove that all known properties that semirings have according to the old definition are preserved.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

无界区域R1上推广的B-BBM方程的整体吸引子

本文研究了无界区域R^1上推广的B—BBM方程的长时间动力学行为，证明了该方程整体吸引子的存在性．     

广义向量均衡问题的解与解集的凸性

引进集值映射的锥真拟凹概念，讨论一类具有集值映射的广义向量衡问题解的存在性与解集的凸性。     

Rough隶属函数关于集合并与交的一种高精度计算方法

近些年来，许多处理近似问题的方法陆续被提出，其中利用Rough集理论计算两个集合的并和交的Rough隶属函数方法是被用较多的一种方法，但毕竟该方法精度较差。为此，介绍了一种精度较高的计算两个集合的并和交的Rough隶属函数方法，它克服了前者利用Rough集理论计算Rough隶属函数的复杂性，而迎来了简单和高精度的特点。     

A strong law of large numbers for generalized random sets from the viewpoint of empirical processes

In this article we prove a strong law of large numbers for Borel measurable nonseparably valued random elements in the case of generalized random sets.

     

Difference Sets and Recursion Theory

There is a recursive set of natural numbers which is the difference set of some recursively enumerable set but which is not the difference set of any recursive set.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by realloeating resources. In this paper, authors consider a machine scheduling problemwith controllable processing times. In the first part of this paper, a special case where the pro-cessing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O（n^2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case, An effective heuristic to the genera/ problem will be presented.